package com.tping.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 *
 * 其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]
 * 阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位
 */
public class Solution_0048 {

    /**
     * 暴力解决方式
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if( len == 0 ) return 0;
        if( len == 1 ) return heights[0];

        int area = 0;
        for (int i = 0; i < len; i++) {
            int j = i, h = heights[i], w = 1;
            // 向左边遍历，找出比当前柱子高的
            while (--j > 0 && heights[j] >= h ){
                w++;
            }

            j = i;

            // 向右边遍历，找出比当前柱子高的
            while ( ++j < len && heights[j] >= h ){
                w++;
            }

            // w 就是计数一下柱子的宽度 * 当前柱子柱子的高度就是当前柱子的最大面积
            area = Math.max(area, w * h);
        }

        return area;
    }

    public static void main(String[] args){
        int[] array = new int[]{2,1,5,6,2,3};
        Solution_0048 solution = new Solution_0048();
        System.out.println("暴力解决方式：" + solution.largestRectangleArea(array));

        System.out.println("单调栈方式解决方式：" + solution.largestRectangleAreaStock(array));
    }

    /**
     * 使用单调栈方式解决
     *
     * @param heights
     * @return
     */
    public int largestRectangleAreaStock(int[] heights){
        int len = heights.length;
        if( len == 0 ) return 0;
        if( len == 1 ) return heights[0];

        int[] newHeights = new int[len + 2];
        for (int i = 0; i < len; i++) {
            newHeights[i + 1] = heights[i];
        }

        // 从新创建一个数组，在数组头和尾设置一个0的值
        heights = newHeights;
        len += 2;
        int area = 0;
        Deque<Integer> stack = new ArrayDeque<Integer>();

        // 栈底添加元素：0
        stack.addLast(0);
        for (int i = 0; i < len; i++) {
            while ( heights[stack.peekLast()] > heights[i] ){
                int height = heights[stack.removeLast()];
                int width = i - stack.peekLast() - 1;
                area = Math.max(area, width * height );
            }

            stack.addLast(i);
        }

        return area;
    }
}
